public class Leetcode {
}
//leetcode:36:有效的数独
class Solution1 {
    //设立两个二维数组存放代表行和列
    boolean[][] row,col;
    //设置一个三维数组代表9宫格
    boolean[][][] gits;
    public boolean isValidSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        gits = new boolean[3][3][10];
        //遍历整个数组
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                //如果值不为'.'
                if(board[i][j] != '.'){
                    //得到这个值
                    int num = board[i][j]-'0';
                    //判断这个值的所在行，列和9宫格是否存在这个数
                    //如果存在就返回false,代表这不是有效的数独
                    if(row[i][num]  || col[j][num]  || gits[i/3][j/3][num]) return false;
                    //如果不存就将这个值所在的行，列和9宫格置为true，代表所在的行，列和9宫格存在这个数
                    row[i][num] =col[j][num] = gits[i/3][j/3][num] = true;

                }
            }
        }
        //最后遍历完整个数组后没有发现不是数独的位置，就返回true
        return true;
    }
}

//leetcode:37:解数独
class Solution2 {
    boolean[][] row, col;
    boolean[][][] gits;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        gits = new boolean[3][3][10];
        //将所有的有数的地方都设置为true
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    //将这个数的行，列，9个格子中此时的num设置为true
                    row[i][num] = col[j][num] = gits[i/3][j/3][num] = true;
                }
            }
        }
        dfs(board);
    }

    public boolean dfs(char[][] board){
        //遍历整个数组
        for(int i = 0;i < 9; i++){
            for(int j = 0;j < 9; j++){
                //如果遇到为'.'的进行更改
                if(board[i][j] == '.'){
                    //更改的数字从1~9获得
                    for(int num = 1; num <= 9; num++){
                        //如果要存入的数字在此时要存放的位置的行，列和所在9宫格不存在，进行存放
                        if(!row[i][num] && !col[j][num] && !gits[i/3][j/3][num]){
                            board[i][j] = (char)(num+'0');
                            //然后将这个数设置为true，代表所在的行，列，9宫格不能存放
                            row[i][num] = col[j][num] = gits[i/3][j/3][num] = true;
                            //如果成功存放就返回true
                            if(dfs(board)) return true;
                            //回溯+剪枝
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = gits[i/3][j/3][num] = false;
                        }
                    }
                    //如果1~9的数字都放完了，还没有合适的就返回false
                    return false;
                }
            }
        }
        //最后所有的'.'都成功的被改成了数字，就返回true
        return true;
    }
}